﻿#include <iostream>

static void zigzagPrint(const int* matrix, const int rowSize, const int colSize)
{
    if (rowSize == 1)
    {
        for (int x = 0; x < colSize; x++)
        {
            printf("%d ", matrix[x]);
        }

        return;
    }

    if (colSize == 1)
    {
        for (int y = 0; y < rowSize; y++)
        {
            printf("%d ", matrix[y]);
        }

        return;
    }

    int x1 = 0;
    int y1 = 0;
    int x2 = 0;
    int y2 = 0;

    bool leftDown = false;
    do 
    {
        if (leftDown)
        {
            for (int x = x1, y = y1; x >= x2, y <= y2; x--, y++)
            {
                printf("%d ", matrix[x + y * colSize]);
            }

            if (x1 + 1 < colSize)
            {
                ++x1;
            }
            else
            {
                ++y1;
            }

            if (y2 + 1 < rowSize)
            {
                ++y2;
            }
            else
            {
                ++x2;
            }
        }
        else
        {
            for (int x = x2, y = y2; x <= x1, y >= y1; x++, y--)
            {
                printf("%d ", matrix[x + y * colSize]);
            }

            if (x1 + 1 < colSize)
            {
                ++x1;
            }
            else
            {
                ++y1;
            }

            if (y2 + 1 < rowSize)
            {
                ++y2;
            }
            else
            {
                ++x2;
            }
        }

        leftDown = !leftDown;
    } while (x1 != x2 || y1 != y2);

    printf("%d", matrix[x1 + y1 * colSize]);
}

/**
 * 用zigzag的方式打印矩阵，比如如下的矩阵:
 *  0  1  2  3
 *  4  5  6  7
 *  8  9 10 11
 *  打印顺序为: 0 1 4 8 5 2 3 6 9 10 7 11
 *
 *  思路：定义两个点, A(x1,y1),B(x2,y2), 这两个点一开始都在左上角。
 *  1. A和B重合，打印重合的点，然后A往右移动，B往下移动；若A不能再右移，则下移；若B不能再下移，则右移
 *  2. A到B沿斜下45°打印元素，然后A往右移动，B往下移动；若A不能再右移，则下移；若B不能再下移，则右移
 *  3. B到A沿斜上45°打印元素，然后A往右移动，B往下移动；若A不能再右移，则下移；若B不能再下移，则右移
 *  ...
 *  4. 直到A和B汇合，打印汇合点，结束
 */
int main_Zigzag()
{
    int colSize = 3;
    int matrix[] = {
        0,4,10,
        1,5,11,
        2,6,12,
        3,8,15,
    };

    int rowSize = sizeof(matrix) / (sizeof(int) * colSize);
    zigzagPrint(matrix, rowSize, colSize);

    return 0;
}